package com.gorkr.labuladong.data_struct.bst;

import org.junit.jupiter.api.Test;

import java.util.Stack;

public class M33ErChaSouSuoShuDeHouXuBianLiXuLieIcof {

    public boolean verifyPostorder(int[] postorder) {
        return verify(postorder,0,postorder.length-1);

    }

    public boolean verify(int[] postorder, int start, int rootIndex
                          ) {
        if(start>=rootIndex){
            return true;
        }
        // 当前根
        int root = postorder[rootIndex];
        int i = rootIndex-1;
        for (; i >=0; i--) {
            if(postorder[i]<root){
                break;
            }
        }
        int rightEnd = rootIndex-1;
        int rightStart = i+1;
        int leftStart = start;
        int leftEnd = i;
        for (int j = leftStart; j <=leftEnd; j++) {
            if(postorder[j]>=root){
                return false;
            }
        }
        return verify(postorder,leftStart,leftEnd)&&verify(postorder,rightStart,rightEnd);
    }

    public boolean verifyPostorder2(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }



    @Test
    public void test(){
        int[] order = {1,6,3,2,5};
        int[] rightOrder = {1,3,2,6,5};
        System.out.println(verifyPostorder2(rightOrder));
    }


}
